// https://leetcode-cn.com/problems/longest-palindromic-substring/
// 给你一个字符串 s，找到 s 中最长的回文子串。

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
// 先翻转字符串，然后对比两个字符串，类似上下两个拉锯，齿轮合适则记录vector<string>结果集当中
public:
    string longestPalindrome(string s) {
        string reverseStr;
        reverseStr.assign(s.begin(), s.end());
        reverse(reverseStr.begin(), reverseStr.end());
        cout << "origin:" << s << endl;
        cout << "revers:" << reverseStr << endl;
        int len = s.size();
        int left = 0;
        string maxString;
        for (int i = 0; i < len; i++) {
            if(maxString.size() > len - i ){
                return maxString;
            }
            maxString = getPalindromeString(s, reverseStr, i, len - 1, maxString);
        }
        return maxString;
/*
        vector <string> res;
        while (left < right) {
            while (left < len - 1 && s[left] != reverseStr[left]) {
                left++;
            }
            while (right > 0 && s[right] != reverseStr[right]) {
                right--;
            }

            if (left < right && s[left] == reverseStr[left] && s[right] == reverseStr[right]) {
                int leftOld = left;
                int rightOld = right;
                cout << "substr:" << s.substr(leftOld, rightOld - leftOld + 1) << endl;
                if (isPalindrome(s, left, right)) {
                    cout << "yes" << endl;
                    cout << "right:" << right << ",left:" << left << endl;
                    cout << "rightOld:" << rightOld << ",leftOld:" << leftOld << endl;

                    res.push_back(s.substr(leftOld, rightOld - leftOld + 1));
                } else {
                    cout << "no" << endl;
                    res.push_back(s.substr(left, leftOld - left + 1));
                    res.push_back(s.substr(rightOld, right - rightOld + 1));
                }
            }
        }

        cout << "res : " << endl;
        for (auto i : res) {
            cout << i << endl;
        }*/
    }

    /*bool isPalindrome(string &s, int &start, int &end) {
        while (start < end) {
            if (s[start] == s[end]) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }*/

    string getPalindromeString(string &originStr, string &reverseStr, int offset, int end, string maxString) {
        string tmp;
        int left = 0;
        while (left + offset <= end) {
            if (originStr[left] == reverseStr[left + offset]) {
                tmp += originStr[left];
            } else {
                if (!tmp.empty()) {
                    if(maxString.size() < tmp.size()){
                        maxString.swap(tmp);
                    }
                    tmp.clear();
                }
            }
            left++;
        }
        if(maxString.size() < tmp.size()){
            maxString.swap(tmp);
        }
        cout << "maxStr:" << maxString << endl;
        left = 0;
        tmp = "";
        while (left + offset <= end) {
            if (originStr[left + offset] == reverseStr[left]) {
                tmp += originStr[left + offset];
            } else {
                if (!tmp.empty()) {
                    if(maxString.size() < tmp.size()){
                        maxString.swap(tmp);
                    }
                    tmp.clear();
                }
            }
            left++;
        }
        if(maxString.size() < tmp.size()){
            maxString.swap(tmp);
        }
        return maxString;
    }
};

int main() {
    Solution so;
//    string s = "abbcddcbbac";
//    string s = "aacabdkacaa";
    string s = "abcdbdkdcba";
    string maxStr = so.longestPalindrome(s);
    cout << "maxStr:" << maxStr << endl;
    return 0;
}